home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DDJMAG / DDJ9212.ZIP / cpptmp.asc < prev    next >
Text File  |  1992-11-30  |  11KB  |  402 lines
  1. _TEMPLATES IN C++_
  2. by Nicholas Wilt
  3.  
  4. [LISTING ONE]
  5. // select.h -- Template-based C++ implementation of the randomized
  6. //   selection algorithm from _Introduction to Algorithms_ by Cormen, 
  7. //   Leiserson and Rivest (pg. 187). Copyright (C) 1992 by Nicholas Wilt.  
  8. //   All rights reserved.
  9.  
  10. template<class T> T
  11. Select(T *base, const int n, int inx)
  12. {
  13.   int left = 0;
  14.   int right = n;
  15.  
  16.   // This while loop terminates when base[left..right]
  17.   // defines a 1-element array.
  18.   while (right != left + 1) {
  19.     // Partition about the q'th element of the array
  20.     int q = left + rand() % (right - left);
  21.  
  22.     T t = base[q];
  23.     base[q] = base[left];
  24.     base[left] = t;
  25.  
  26.     // Partition about base[left]; all elements less than
  27.     // base[left] get swapped into the left-hand side of
  28.     // the array.
  29.     int i = left - 1;
  30.     int j = right;
  31.     while (j >= i) {
  32.       while (j > 0 && t < base[--j]);
  33.       while (i < (right-1) && base[++i] < t);
  34.       if (i < j) {
  35.     T t = base[i];
  36.     base[i] = base[j];
  37.     base[j] = t;
  38.       }
  39.     }
  40.     // Now focus attention on the partition containing
  41.     // the order statistic we're interested in.
  42.     if (inx <= j - left)
  43.       // Throw away the right-hand partition; we know it
  44.       // doesn't contain the i'th order statistic.
  45.       right = j + 1;
  46.     else {
  47.       // Throw away the left-hand partition; we know it
  48.       // doesn't contain the i'th order statistic.
  49.       // Now we're looking for the inx - j - left + 1'th
  50.       // order statistic of the right-hand partition.
  51.       inx -= j - left + 1;
  52.       left = j + 1;
  53.     }
  54.   }
  55.   // base[left] is the element we want, return it.
  56.   return base[left];
  57. }
  58.  
  59.  
  60. [LISTING TWO]
  61.  
  62. // select.cpp -- Demonstrates the use of the Select function template on 
  63. //   arrays of integers and Point2D's. It generates a random of array of 
  64. //   integers, then enumerates the order statistics from 0..n-1. This will 
  65. //   print out the members of the array in sorted order. This isn't a 
  66. //   suggestion for how to use Select (obviously it's more efficient to sort 
  67. //   the array if you want to print out the members in sorted order!) but it's
  68. //   good to enumerate them all to verify that algorithm is working properly.
  69. //   The other class the program deals with is a used-defined Point2D class.
  70. //   This is a two-dimensional point defined by two floating-point numbers. 
  71. //   The ordering chosen, defined by the operator< for the class, is a 
  72. //   standard topological ordering from computational geometry.
  73. //   Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.
  74.  
  75. #include <fstream.h>
  76. #include <iomanip.h>
  77. #include <stdlib.h>
  78. #include "select.h"
  79.  
  80. // Just for fun, here's a signum template function. Returns -1 if a < b; 1 if 
  81. // b < a; 0 if they're equal. I've ensured only operator< is used for 
  82. // comparisons, so operator> isn't defined for a user-defined class.
  83. template<class T> int
  84. Signum(T a, T b)
  85. {
  86.   if (a < b)         return -1;
  87.   else if (b < a)    return 1;
  88.   else           return 0;
  89. }
  90. class Point2D {
  91.   double x, y;
  92. public:
  93.   Point2D() { }
  94.   Point2D(double X, double Y): x(X), y(Y) { }
  95.  
  96.   // operator< makes our points sorted in topological order: increasing order 
  97.   // in x, and increasing order in y if there is a tie in x.
  98.   friend int operator<(const Point2D& x, const Point2D& y) {
  99.     int ret = Signum(x.x, y.x);
  100.     return (ret) ? ret < 0 : Signum(x.y, y.y) < 0;
  101.   }
  102.   friend ostream& operator<< (ostream& a, Point2D& b) {
  103.     a << "(" << b.x << ", " << b.y << ")";
  104.     return a;
  105.   }
  106. };
  107. // Number of elements to allocate in the test arrays
  108. const int NumInts = 10;
  109. const int NumPts = 5;
  110. int
  111. main()
  112. {
  113.   int *x = new int[NumInts];
  114.   int i;
  115.   for (i = 0; i < NumInts; i++) {
  116.     x[i] = rand() % 100;
  117.     cout << x[i] << ' ';
  118.   }
  119.   cout << '\n';
  120.   for (i = 0; i < NumInts; i++) {
  121.     cout << Select(x, NumInts, i) << ' ';
  122.   }
  123.   cout << '\n';
  124.   delete x;
  125.   Point2D *y = new Point2D[NumPts];
  126.   cout << setprecision(2);
  127.   for (i = 0; i < NumPts; i++) {
  128.     y[i] = Point2D( (double) rand() * 10.0 / RAND_MAX,
  129.             (double) rand() * 10.0 / RAND_MAX);
  130.     cout << y[i] << ' ';
  131.   }
  132.   cout << '\n';
  133.   for (i = 0; i < NumPts; i++) {
  134.     cout << Select(y, NumPts, i) << ' ';
  135.   }
  136.   cout << '\n';
  137.   return 0;
  138. }
  139.  
  140.  
  141. [LISTING THREE]
  142.  
  143. // bintree.h -- Header file for simple binary tree class template.
  144. //   Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.
  145. //  BinaryNode is a helper class template for the BinaryTree class template. It
  146. //  should be needed only rarely by the end user of the BinaryTree class, if 
  147. //  ever. BinaryTree<T> is BinaryNode<T>'s friend. The only other classes that 
  148. //  can access BinaryNode's data are classes for which it is a base class.
  149. template<class T>
  150. class BinaryNode {
  151. protected:
  152.   T x;
  153.   BinaryNode<T> *left, *right;
  154. public:
  155.   BinaryNode(const T& X): x(X) {
  156.     left = right = 0;
  157.   }
  158.   BinaryNode(const T& X, BinaryNode<T> *l, BinaryNode<T> *r): x(X) {
  159.     left = l;
  160.     right = r;
  161.   }
  162.   friend class BinaryTree<T>;
  163. }
  164. // BinaryTree manipulates binary trees described by pointers to BinaryNode.
  165. template<class T>
  166. class BinaryTree {
  167. protected:
  168. // Pointer to the root node of the binary tree.
  169.   BinaryNode<T> *root;
  170. // Various functions to manipulate collections of binary
  171. // tree nodes.  These are the functions that do the real work.
  172.   static BinaryNode<T> *InsertNode(BinaryNode<T> *r, T x);
  173.   static BinaryNode<T> *DupNode(BinaryNode<T> *r);
  174.   static void PostOrderDeletion(BinaryNode<T> *r);
  175.   static T *QueryNode(BinaryNode<T> *r, const T& x);
  176.   static void PreOrderNode(BinaryNode<T> *r, void (*f)(T *));
  177.   static void InOrderNode(BinaryNode<T> *r, void (*f)(T *));
  178.   static void PostOrderNode(BinaryNode<T> *r, void (*f)(T *));
  179. public:
  180.   // Constructors and assignment operator
  181.   BinaryTree() { root = 0; }
  182.   // Copy constructor duplicates all the nodes in the tree.
  183.   BinaryTree(BinaryTree<T>& x) { root = DupNode(x.root); }
  184.   // Assignment operator deletes nodes already there, then
  185.   // copies the ones in the tree to be copied.
  186.   BinaryTree<T>& operator=(const BinaryTree<T>& x) {
  187.     PostOrderDeletion(root);
  188.     root = DupNode(x.root);
  189.     return *this;
  190.   }
  191.   // Destructor frees all the nodes in the binary tree.
  192.   ~BinaryTree() { PostOrderDeletion(root);  }
  193.   // Inserts a node containing x into the binary tree.
  194.   void Insert(const T& x) { root = InsertNode(root, x); }
  195.   // Returns a pointer to node equal to x, if in tree.
  196.   // If none found Query returns 0.
  197.   T *Query(const T& x) { return QueryNode(root, x); }
  198.  
  199.   // Various traversal functions perform the traversal
  200.   // in the order given and call f with a pointer to the
  201.   // node contents when visiting.
  202.   void PreOrder(void (*f)(T *)) { PreOrderNode(root, f); }
  203.   void InOrder(void (*f)(T *)) { InOrderNode(root, f); }
  204.   void PostOrder(void (*f)(T *)) { PostOrderNode(root, f); }
  205. };
  206. // The following function declarations give examples of how to
  207. // write function templates for member functions.
  208. // Deletes the tree pointed to by r.
  209. template<class T> void
  210. BinaryTree<T>::PostOrderDeletion(BinaryNode<T> *r)
  211. {
  212.   if (r) {
  213.     PostOrderDeletion(r->left);
  214.     PostOrderDeletion(r->right);
  215.     delete r;
  216.   }
  217. }
  218. // Inserts a node with key x into the binary tree with the
  219. // root given, and returns the new root.
  220. template<class T> BinaryNode<T> *
  221. BinaryTree<T>::InsertNode(BinaryNode<T> *r, T x)
  222. {
  223.   if (r) {
  224.     if (x < r->x)
  225.       r->left = InsertNode(r->left, x);
  226.     else
  227.       r->right = InsertNode(r->right, x);
  228.   }
  229.   else
  230.     r = new BinaryNode<T>(x);
  231.   return r;
  232. }
  233. // Duplicates the binary tree given and returns pointer to the new root.
  234. template<class T> BinaryNode<T> *
  235. BinaryTree<T>::DupNode(BinaryNode<T> *r)
  236. {
  237.   if (r)
  238.     return new BinaryNode<T>(r->x,
  239.                  DupNode(r->left),
  240.                  DupNode(r->right));
  241.   else
  242.     return 0;
  243. }
  244. // Returns pointer to key given, if found in binary tree. Otherwise returns 0.
  245. template<class T> T *
  246. BinaryTree<T>::QueryNode(BinaryNode<T> *r, const T& x)
  247. {
  248.   if (r) {
  249.     if (x == r->x)
  250.       return &r->x;
  251.     if (x < r->x) return QueryNode(r->left, x);
  252.     else      return QueryNode(r->right, x);
  253.   }
  254.   else
  255.     return 0;
  256. }
  257. // Traversal functions. These three functions traverse the tree and call the 
  258. // pointer to function on the node contents when it's time to visit the node.
  259. template<class T> void
  260. BinaryTree<T>::PreOrderNode(BinaryNode<T> *r, void (*f)(T *))
  261. {
  262.   if (r) {
  263.     (*f)(&r->x);
  264.     PreOrderNode(r->left, f);
  265.     PreOrderNode(r->right, f);
  266.   }
  267. }
  268. template<class T> void
  269. BinaryTree<T>::InOrderNode(BinaryNode<T> *r, void (*f)(T *))
  270. {
  271.   if (r) {
  272.     InOrderNode(r->left, f);
  273.     (*f)(&r->x);
  274.     InOrderNode(r->right, f);
  275.   }
  276. }
  277. template<class T> void
  278. BinaryTree<T>::PostOrderNode(BinaryNode<T> *r, void (*f)(T *))
  279. {
  280.   if (r) {
  281.     PostOrderNode(r->left, f);
  282.     PostOrderNode(r->right, f);
  283.     (*f)(&r->x);
  284.   }
  285. }
  286.  
  287.  
  288.  
  289.  
  290. [LISTING FOUR]
  291.  
  292. // bintree.cpp -- Demonstration program for BinaryTree class template. Inserts 
  293. //  10 random numbers into a BinaryTree<int>, prints them out and then prints 
  294. //  out the pre-, in- and post-order traversals of the resulting binary tree.
  295. //  Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.
  296.  
  297. #include <iostream.h>
  298. #include <stdlib.h>
  299. #include <alloc.h>
  300.  
  301. #include "bintree.h"
  302.  
  303. // Passed to BinaryTree<int> traversal functions. This gets called with a 
  304. // pointer to the node contents (int in this case, since it's a 
  305. // BinaryTree<int>) whenever it's time to visit a node in the tree.
  306. void
  307. PrintInt(int *x)
  308. {
  309.   cout << *x << ' ';
  310. }
  311. int
  312. main()
  313. {
  314.   int i;
  315.   BinaryTree<int> tree;
  316.   cout << "Insertion:\t";
  317.   for (i = 0; i < 10; i++) {
  318.     int insertme = rand() % 100;
  319.     tree.Insert(insertme);
  320.     cout << insertme << ' ';
  321.   }
  322.   cout << '\n';
  323.   cout << "Pre-order:\t";  tree.PreOrder(PrintInt);  cout << '\n';
  324.   cout << "In-order:\t";   tree.InOrder(PrintInt);   cout << '\n';
  325.   cout << "Post-order:\t"; tree.PostOrder(PrintInt); cout << '\n';
  326.   return 0;
  327. }
  328.  
  329.  
  330. Example 1: Declaring a function template
  331.  
  332. template<template parameters>
  333. return value               // From here on we define
  334. name(function parameters) {    // the function in terms of
  335.   function body            // the template parameters.
  336. }
  337.  
  338.  
  339.  
  340.  
  341. Example 2: (a) defining a template-based Select function; (b) calling the Select function
  342.  
  343. (a)
  344.  
  345. template<class T> T
  346. Select(T *base, const int n, int i)
  347. {
  348.     // Implementation
  349. }
  350.  
  351.  
  352. (b)
  353.  
  354.     int *arr, n;
  355.     // ... allocate array and set n
  356.     // Set penultimate to the second-largest element in arr.
  357.     int penultimate = Select(arr, n, n - 2);
  358.  
  359. (c)
  360.  
  361. int
  362. Select(int *x, const int n, int i)
  363. {
  364.   // Own function definition of Select<int>
  365. }
  366.  
  367.  
  368.  
  369. Example 3
  370.  
  371. (a)
  372.  
  373. template<class T>
  374. class BinaryNode {
  375.   T x;              // Contents of node
  376.   BinaryNode<T> *left, *right;  // Left and right children
  377. //etc.
  378. };
  379.  
  380.  
  381. (b)
  382.  
  383. // Class template for a binary tree node including a
  384. // pointer to the parent.
  385. template<class T>
  386. class BinaryNodeWithParent : public BinaryNode<T> {
  387.   BinaryNodeWithParent<T> *parent;
  388. // etc.
  389. };
  390.  
  391.  
  392. (c)
  393.  
  394. template<class T, int Size>
  395. class Vector {
  396.   T x[Size];       // Vector contains Size T's.
  397. // etc.
  398. };
  399.  
  400.  
  401.  
  402.